A DC Programming Approach for Solving Multicast Network Design Problems via the Nesterov Smoothing Technique

摘要

This paper continues our effort initiated in [9] to study MulticastCommunication Networks, modeled as bilevel hierarchical clustering problems, byusing mathematical optimization techniques. Given a finite number of nodes, weconsider two different models of multicast networks by identifying a certainnumber of nodes as cluster centers, and at the same time, locating a particularnode that serves as a total center so as to minimize the total transportationcost through the network. The fact that the cluster centers and the totalcenter have to be among the given nodes makes this problem a discreteoptimization problem. Our approach is to reformulate the discrete problem as acontinuous one and to apply Nesterov smoothing approximation technique on theMinkowski gauges that are used as distance measures. This approach enables usto propose two implementable DCA-based algorithms for solving the problems.Numerical results and practical applications are provided to illustrate ourapproach.